1690G - Count the Trains - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define loop(i, a, n) for (int i = a; i < n; i++)
#define loope(i, b, n) for (int i = b; i <= n; i++)
#define loopit(a) for (auto it = a.begin(); it != a.end(); it++)
#define bloop(i, a, b) for (int i = a; i > b; i--)
#define bloope(i, a, b) for (int i = a; i >= b; i--)
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define MP make_pair
#define pi pair<int, int>
#define ff first
#define ss second
#define PQ priority_queue<int> pq;
#define vi vector<int>
#define vii vector<vector<int>>
#define vil vector<ll>
#define viil vector<vector<ll>>
#define si set<int>
#define NO cout<<"NO\n";
#define YES cout<<"YES\n";
#define MPQ priority_queue<pi, vector<int>, greater<pi>> mpq;
#define io                        \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#ifdef MURTAZAS_BUILD
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

void solve() {
    int n, m; cin >> n >> m;
    vi a(n);
    set<int, greater<int>>vals;
    set<int>inds;

    loop(i, 0, n) {
        cin >> a[i];
        if (!vals.size() || a[i] < (*vals.rbegin())) {
            vals.insert(a[i]);
            inds.insert(i);
        }
    }

    debug(vals);
    debug(inds);

    loop(i, 0, m) {
        int in, dec; cin >> in >> dec;
        in--;

        int cur = a[in] - dec;

        auto it = inds.upper_bound(in);

        int pind = *prev(it, 1);

        int val = a[pind];

        if (cur < val) {

            if (in == pind) {
                vals.erase(a[in]);
                inds.erase(in);
            }

            while (it != inds.end() && a[*it] >= cur) {

                auto nx = next(it, 1);

                int rind = *it;
                inds.erase(rind);
                vals.erase(a[rind]);

                it = nx;
            }

            vals.insert(cur);
            inds.insert(in);

            debug(vals);
            debug(inds);
        }

        a[in] = cur;
        cout << vals.size() << " ";
    }
    cout << "\n";
}

int main() {
    io;
#ifdef MURTAZAS_BUILD
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    int test = 1, i = 0;
    cin >> test;
    while (i++ != test) {
        // cout<<"Case #"<<i<<": ";

        debug(i, test);
        solve();
    }

#ifdef  MURTAZAS_BUILD
    cerr << "Time Taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds" << endl;
#endif

    return 0;
}